# !/usr/bin/env/ python3
# -*- coding: utf-8 -*-

import numpy as np

"""
找到一个与密码完全相同的字符串
"""

class GeneticAlgorithm(object):
	""" 遗传算法

	Parameters:
	----------------
	cross_rate: float
		交配的可能性大小
	mutate_rate: float
		基因突变的可能性大小
	n_population: int
		种群的大小
	n_iterations: int
		迭代的次数
	password: str
		欲破解的密码
	"""
	def __init__(self, cross_rate, mutation_rate, n_population, n_iterations, password):
		self.cross_rate = cross_rate
		self.mutate_rate = mutation_rate
		self.n_population = n_population
		self.n_iterations = n_iterations
		self.password = password											 # 要破解的密码
		self.password_size = len(self.password)								 # 要破解密码的长度
		self.password_ascii = np.fromstring(self.password, dtype = np.uint8) # 将 password 转换成 ASCII
		self.ascii_bounder = [32, 126 + 1]

	def init_population(self):
		"""
		初始化一个种群
		"""
		population = np.random.randint(low = self.ascii_bounder[0], high = self.ascii_bounder[1],
			size = (self.n_population, self.password_size)).astype(np.int8)
		return population

	def translateDNA(self, DNA):
		"""
		将个体的 DNA 转换成 ASCII
		"""
		return DNA.tostring().decode('ascii')

	def fitness(self, population):
		"""
		计算种群中每个个体的适应度，适应度越高，说明该个体的基因越好
		"""
		match_num = (population == self.password_ascii).sum(axis = 1)
		return match_num
	
	def select(self, population):
		"""
		对这种群按照其适应度进行采样，这样适应度高的个体就会以更高的概率被选择
		"""
		fitness = self.fitness(population) + 1e-4 # 下一步抽样的过程中用到了除法，出现除法就要考虑到分母为0的特殊情况
		idx = np.random.choice(np.arange(self.n_population), size = self.n_population, replace = True, p = fitness / fitness.sum())
		return population[idx]

	def create_child(self, parent, pop):
		"""
		进行交配
		"""
		if np.random.rand() < self.cross_rate:
			index = np.random.randint(0, self.n_population, size=1)
			cross_points = np.random.randint(0, 2, self.password_size).astype(np.bool)
			parent[cross_points] = pop[index, cross_points]
		return parent

	def mutate_child(self, child):
		"""
		基因突变
		"""
		for point in range(self.password_size):
			if np.random.rand() < self.mutate_rate:
				child[point] = np.random.randint(*self.ascii_bounder) # 选取一个随机 ASCII 下标
		return child

	def evolution(self):
		"""
		进化
		"""
		population = self.init_population()
		for i in range(self.n_iterations):
			fitness = self.fitness(population)

			best_person = population[np.argmax(fitness)]
			best_person_ascii = self.translateDNA(best_person)

			if i % 10 == 0:
				print(u'第%-4d次进化后, 基因最好的个体(与欲破解的密码最接近)是: \t %s'% (i, best_person_ascii))
				
			if best_person_ascii == self.password:
				print(u'第%-4d次进化后, 找到了密码: \t %s'% (i, best_person_ascii))
				break

			population = self.select(population)
			population_copy = population.copy()

			for parent in population:
				child = self.create_child(parent, population_copy)
				child = self.mutate_child(child)
				parent[:] = child
		
			population = population

def main():
    password = 'I think say !'     # 要破解的密码
    
    ga = GeneticAlgorithm(cross_rate=0.8, mutation_rate=0.01, n_population=300, n_iterations=500, password=password)
    
    ga.evolution()

if __name__ == '__main__':
    main()